package com.cdream.basic.algorithm.leetcode.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cdream
 * @date 6/10/21
 */
public class Question54 {
    public static void main(String[] args) {
        System.out.println(new Question54().spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] used = new boolean[m][n];
        int total = m * n;
        int[] start = {0, 0};
        int dir = 0;
        List<Integer> res = new ArrayList<>();
        boolean add = true;
        while (res.size() != total) {
            int x = start[0];
            int y = start[1];
            int element = matrix[x][y];
            if (add) {
                res.add(element);
                used[x][y] = true;
            }
            //右
            if (dir == 0) {
                if (y + 1 < n && !used[x][y + 1]) {
                    start[1] = y + 1;
                    add = true;
                } else {
                    dir = 1;
                    add = false;
                }
                // 下
            } else if (dir == 1) {
                if (x + 1 < m && !used[x + 1][y]) {
                    start[0] = x + 1;
                    add = true;
                } else {
                    dir = 2;
                    add = false;
                }
                // 左
            } else if (dir == 2) {
                if (y - 1 >= 0 && !used[x][y - 1]) {
                    start[1] = y - 1;
                    add = true;
                } else {
                    dir = 3;
                    add = false;
                }
                // 上
            } else {
                if (x - 1 >= 0 && !used[x - 1][y]) {
                    start[0] = x - 1;
                    add = true;
                } else {
                    dir = 0;
                    add = false;
                }
            }
        }
        return res;
    }
}
